package com.jeff.learn.recursion;

/**
 * 递归实现冒泡排序
 *
 * @author yaojianfeng
 */
public class RecursionBubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        bubbleSort(arr, arr.length - 1);
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    /**
     * 冒泡排序
     *
     * @param arr      数组
     * @param maxIndex 递归算法中未排序的右边界,也就是未排序范围的最大索引值 初始值是数组的长度-1
     */
    public static void bubbleSort(int[] arr, int maxIndex) {
        // 递归终止条件
        if (maxIndex == 0) {
            return;
        }
        // 进行升序冒泡排序
        for (int i = 0; i < maxIndex; i++) {
            // 进行标记,如果没有进行交换,说明已经有序,不需要再继续排序 缩小未排序范围 提升效率
            int sortFlag = 0;
            // 进行交换 如果前面的数比后面的数大 则交换
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sortFlag = i;
            }
            //缩小未排序范围,进行下一轮排序
            bubbleSort(arr, sortFlag);
        }
    }

}
